// 我们从二叉树的根节点 root 开始进行深度优先搜索。
// 在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。
// （如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。
// 如果节点只有一个子节点，那么保证该子节点为左子节点。
// 给出遍历输出 S，还原树并返回其根节点 root。

var recoverFromPreorder: (S: string) => TreeNode = function (S) {
    const stack: TreeNode[] = [];// 声明栈
    let index: number = 0;// 声明索引下标
    while (index < S.length) {
        let depth: number = 0;
        // 计算节点深度
        while (index < S.length && S[index] === "-") {
            depth++;
            index++;
        }
        let startIndex: number = index;// 开始索引
        // 计算当前数字的值
        while (index < S.length && S[index] !== "-") {
            index++;
        }
        let currNum: number = parseInt(S.slice(startIndex, index));// 取得当前数字
        let currNode: TreeNode = new TreeNode(currNum);// 生成当前叶节点
        if (stack.length < 1) stack.push(currNode);// 根节点入栈判断
        // 如果当前节点与栈顶节点为父子关系，直接插到左叶节点上
        if (depth === stack.length) {
            stack[stack.length - 1].left = currNode;
        } else {// 反之，由题意可得，该节点一定为栈中某位置路径上的右叶节点
            while (depth !== stack.length) {
                stack.pop();
            }// 安全检测
            if (stack.length >= 1) stack[stack.length - 1].right = currNode;
        }
        stack.push(currNode);// 当前节点入栈
    }
    return stack[0];
};

// 总的来说这道题目的难度还是比较大的
// 题目中不允许使用递归，那么从底层思考
// 很明显可以想到利用栈来模拟递归实现
// 首先是基本的操作
// 我们每次从字符串 s 中取出一个节点的值以及它的深度信息。具体实现上：
// 我们首先读取若干个字符 -，直到遇到非 - 字符位置。通过 - 的个数，我们就可以知道当前节点的深度信息；
// 我们再读取若干个数字，直到遇到非数字或者字符串的结尾。通过这些数字，我们就可以知道当前节点的值。
// 得到这些信息后就可以构造出一个当前的树节点，之后需要考虑将当前的节点放在何处。
// 记当前节点为 T，上一个节点为 S，实际上只有两种情况：
// 1、T是S的左叶节点
// 2、T 是根节点到 S 这一条路径上（不包括 S）某一个节点的右子节点。
// （因为题目中规定了如果节点只有一个子节点，那么保证该子节点为左子节点。
// 在 T 出现之前，S 仍然还是一个叶节点，没有左子节点，因此 T 如果是 S 的子节点，一定是优先变成 S 的左子节点）。
// 之后的操作就是模拟这一构造的过程，不要遗漏一些细节上的处理，
// 例如索引的下标越界、根节点的处理、入栈出栈的时机


